import functools


class Solution(object):
    def minCost(self, n, cuts):
        st = []
        cuts.sort()
        for i in range(len(cuts)):
            if i == 0:
                st.append(cuts[i])
            else:
                st.append(cuts[i] - cuts[i - 1])
        st.append(n - cuts[-1])
        m = len(st)
        prefix = st.copy()
        for i in range(1, m):
            prefix[i] += prefix[i - 1]

        @functools.cache
        def dfs(i, j):
            if i == j:
                return 0
            else:
                if i == 0:
                    val = prefix[j]
                else:
                    val = prefix[j] - prefix[i - 1]
                min_val = float('inf')
                for k in range(i, j):
                    min_val = min(min_val, dfs(i, k) + dfs(k + 1, j))
                return min_val + val

        return dfs(0, m - 1)


data = Solution()
n = 9
cuts = [5, 6, 1, 4, 2]
print(data.minCost(n, cuts))
